package leetcode.offer.tree;

import leetcode.tree.common.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 *
 * @author mazouri
 * @create 2021-09-25 23:47
 */
public class _34__pathSum {
    LinkedList<Integer> track = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();
    int target;
    int sum = 0;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        this.target = target;
        dfs(root);
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;

        track.add(root.val);
        sum += root.val;
        if (sum == target && root.left == null && root.right == null) {
            res.add(new LinkedList<>(track));
        }
        dfs(root.left);
        dfs(root.right);
        sum -= root.val;
        track.removeLast();
    }

//    private void dfs(TreeNode root, int target) {
//        if (root == null) return;
//        target -= root.val;
//
//        track.add(root.val);
//        if (target == 0 && root.right == null && root.left == null) {
//            res.add(new LinkedList<>(track));
//            return;
//        }
//
//        dfs(root.left, target);
//        dfs(root.right, target );
//        track.removeLast();
//    }
}
